package videoExercises;

public class sort {
    public static void main(String[] args) {

        //冒泡排序
        //int[] arr = {3,5,1,9,6,2};
        /*for(int j = 0 ;j <arr.length-1; j++){
            for(int i = 0;i < arr.length-1-j;i++){
                if(arr[i] > arr[i+1]){
                    int temp = arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1] = temp;
                }
            }
        }

        for(int i =0 ; i<arr.length ;i++){
            System.out.print(arr[i]);
        }*/

        //选择排序
        /*for(int j =0;j<arr.length-1;j++){
            for(int i=j+1;i<arr.length ;i++){
                if(arr[j]>arr[i]){
                    int temp = arr[j];
                    arr[j] = arr[i];
                    arr[i]=temp;
                }
            }
        }

        for(int i =0 ; i<arr.length ;i++){
            System.out.print(arr[i]);
        }*/

        //插入排序
        /*int[] arr2={3,8,5,1,7,4,12,6,9,2};
        int startIndex = -1;
        for(int i = 0 ;i<arr2.length ;i++){
            if(arr2[i] > arr2[i+1]){
                startIndex = i+1;
                break;
            }
        }
        for(int i = startIndex ; i<arr2.length;i++){

            int j =i;

           while(j>0 &&arr2[j]<arr2[j-1]){
               int temp =arr2[j];
               arr2[j] = arr2[j-1];
               arr2[j-1]=temp;
               j--;
           }
        }

        for(int i =0 ; i<arr2.length ;i++){
            System.out.print(arr2[i]+" ");
        }*/

        //利用递归求1到100的和
        /*int number=100;
        int sum1 = sum(100);
        System.out.println(sum1);*/

        // 利用递归求阶乘的和
        /*int a=5;
        int i = factorialSumming(a);
        System.out.println(i);*/

        //快速排序
        int[] arr = {5,4,6,8,10,11,7,12,25,16,13};
        quickSort(arr,0,arr.length-1);
        long endTime =System.currentTimeMillis();
        for(int i =0 ; i<arr.length ;i++){
            System.out.print(arr[i]+" ");
        }

    }
     //求1到100的和的方法
    /*public static int sum(int number){
        if(number == 1){
            return 1;
        }else{
        return number+sum(number-1);
        }
    }*/

    //求阶乘的和的方法
    /*public static int factorialSumming(int a){
        if(a==1){
            return 1;
        }else {
            return a * factorialSumming(a - 1);
        }
    }*/

    public static void quickSort(int[] arr ,int i,int j){
        int start =i;
        int end =j;
        if(start > end){
           return;
        }
        int baseNumber =arr[i];
        while(start != end){
            while(true){
                if(end<=start || arr[end]<baseNumber){
                    break;
                }
                end--;
            }
            while(true){
                if(end<=start || arr[start]>baseNumber){
                    break;
                }
                start++;
            }
            int temp = arr[start];
            arr[start] =arr[end];
            arr[end] =temp;
        }
        int temp =arr[i];
        arr[i]=arr[end];
        arr[end]=temp;

        quickSort(arr,i,end-1);
        quickSort(arr,start+1,j);
    }

}
